Histograms can be used for selectivity estimation during database query optimization in data processing applications. Histogram compression into fewer intervals enables faster histogram processing and thus faster query optimization but at the cost of reduced accuracy. Trends (for example ever-increasing monthly sales) make histograms inherently inaccurate. In conventional system, the inaccuracy can be reduced only by increasing the number of intervals. Periodic patterns (for example, weekly sales spiking on Friday but dropping on Monday) cannot be captured in histograms unless multiple intervals are dedicated for each period.
Conventional systems either accept large histograms resulting in slow query optimization, or have inaccurate selectivity estimation and thus unreliable selection among alternative query plans.